package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/maximum-width-of-binary-tree/">二叉树最大宽度(Maximum Width of Binary Tree)</a>
 * <p>给你一棵二叉树的根节点 root ，返回树的 最大宽度 。</p>
 * <p>树的 最大宽度 是所有层中最大的 宽度 。</p>
 * <p>每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。</p>
 * <p>题目数据保证答案将会在  32 位 带符号整数范围内。</p>
 * </p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,3,2,5,3,null,9]
 *                      1
 *                    /   \
 *                   3     2
 *                  / \     \
 *                 5   3     9
 *      输出：4
 *      解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
 *
 * 示例 2：
 *      输入：root = [1,3,2,5,null,null,9,6,null,7]
 *                         1
 *                       /   \
 *                      3     2
 *                     /       \
 *                    5         9
 *                   /         /
 *                  6         7
 *      输出：7
 *      解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
 *
 * 示例 3：
 *      输入：root = [1,3,2,5]
 *                          1
 *                         / \
 *                        3   2
 *                       /
 *                      5
 *      输出：2
 *      解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目范围是 [1, 3000]</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/17 9:26
 */
public class LC0662MaximumWidthOfBinaryTree_M {

    static class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            int maxWidth = 0;
            if (root == null) {
                return maxWidth;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            Map<TreeNode, Integer> indexMap = new HashMap<>();
            queue.addLast(root);
            indexMap.put(root, 1);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                int i1 = indexMap.get(queue.peekLast()) - indexMap.get(queue.peekFirst()) + 1;
                maxWidth = Math.max(maxWidth, i1);
                for (int i = 1; i <= currLevelNodeSize; i++) {
                    TreeNode currNode = queue.pollFirst();
                    Integer index = indexMap.get(currNode);
                    if (currNode.left != null) {
                        queue.addLast(currNode.left);
                        indexMap.put(currNode.left, index * 2);
                    }
                    if (currNode.right != null) {
                        queue.addLast(currNode.right);
                        indexMap.put(currNode.right, index * 2 + 1);
                    }
                }
            }
            return maxWidth;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(5);
        root1.left.right = new TreeNode(3);
        root1.right.right = new TreeNode(9);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(3);
        root2.right = new TreeNode(2);
        root2.left.left = new TreeNode(5);
        root2.left.left.left = new TreeNode(6);
        root2.right.right = new TreeNode(9);
        root2.right.right.left = new TreeNode(7);

        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(3);
        root3.right = new TreeNode(2);
        root3.left.left = new TreeNode(5);

        TreeNode root4 = new TreeNode(1);
        root4.left = new TreeNode(3);
        root4.right = new TreeNode(2);
        root4.left.left = new TreeNode(5);
        root4.right.right = new TreeNode(9);
        root4.right.right.right = new TreeNode(7);

        Solution solution = new Solution();
        System.out.println(solution.widthOfBinaryTree(root1));
        System.out.println(solution.widthOfBinaryTree(root2));
        System.out.println(solution.widthOfBinaryTree(root3));
        System.out.println(solution.widthOfBinaryTree(root4));
    }
}
